package CommonAlgs.DP;

/**
 * @Author ChanZany
 * @Date 2021/5/14 10:20
 * @Version 1.0
 * 给定一个数组 ，让你找出一个最长上升子序列的长度，这样的子序列是允许中间越过一些字符的，即留“空”。
 * 例如a=[1,5,3,4,8]
 * 答案为4：[1,3,4,8]。
 * 解法：
 * 1. 设计状态
 * 记f(x)为以a[x]结尾的LIS长度，那么LIS=max{f(x)}
   如：x = [1,2,3,4,5]
     a[x]=[1,5,3,4,0]
     则 f(1)=1 f(2)=2 f(3)=2 f(4)=3 f(5)=1
 * 2. 推导f(x)
 *  考虑比x小的每一个p,若a[x]>a[p]，则f(x)=f(p)+1

 * 3. 状态转移方程
 * f(x)=max{f(p)}+1
 */
public class LIS {

    public static void main(String[] args) {

        int[] input = {1, 5, 3, 4, 0};
        int ret = mySolution(input);
        System.out.println(ret);
    }

    public static int mySolution(int[] a){
        int[] dp = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            dp[i]=1;                        //f(x)的一种解 f(x)=1
            for (int j = 0; j < i; j++) { //考虑比x小的每一个p,若a[x]>a[p]，则f(x)=f(p)+1
                if (a[j]<a[i]) dp[i]=Math.max(dp[i],dp[j]+1); //f(x)的另一种解f(x)=max{f(p)}+1
            }
            System.out.printf("dp[%d]=%d\n",i,dp[i]);
        }
        return max(dp);
    }

    private static int max(int[] dp) {
        int ret = 0;
        for (int i : dp) {
            if (i>ret) ret = i;
        }
        return ret;
    }


}
